翻訳と辞書 Words near each other ・ Lined pocket mouse ・ Lined pocketbook ・ Lined quail-dove ・ Linear feedback shift register ・ Linear filter ・ Linear Flash ・ Linear flow on the torus ・ Linear focal elastosis ・ Linear form ・ Linear fractional transformation ・ Linear function ・ Linear function (calculus) ・ Linear genetic programming ・ Linear gingival erythema ・ Linear grammar ・ Linear hashing ・ Linear Heat Detection ・ Linear IgA bullous dermatosis ・ Linear independence ・ Linear induction motor ・ Linear inequality ・ Linear Integrated Systems ・ Linear interpolation ・ Linear ion trap ・ Linear least squares ・ Linear least squares (mathematics) ・ Linear Lie algebra ・ Linear logic ・ Linear low-density polyethylene ・ Linear map Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Linear hashing ： ウィキペディア英語版 Linear hashing Linear hashing is a dynamic hash table algorithm invented by Witold Litwin (1980), and later popularized by Paul Larson. Linear hashing allows for the expansion of the hash table one slot at a time. The frequent single slot expansion can very effectively control the length of the collision chain. The cost of hash table expansion is spread out across each hash table insertion operation, as opposed to being incurred all at once. Linear hashing is therefore well suited for interactive applications. ==Algorithm Details== First the initial hash table is set up with some arbitrary initial number of buckets. The following values need to be kept track of: * $N$: The initial number of buckets. * $L$: The current level which is an integer that indicates on a logarithmic scale approximately how many buckets the table has grown by. This is initially $0$. * $S$: The step pointer which points to a bucket. It initially points to the first bucket in the table. Bucket collisions can be handled in a variety of ways but it is typical to have space for two items in each bucket and to add more buckets whenever a bucket overflows. More than two items can be used once the implementation is debugged. Addresses are calculated in the following way: * Apply a hash function to the key and call the result $H$. * If $H\; \backslash bmod\; (N\; \backslash times\; 2^L)$ is an address that comes before $S$, the address is $H\; \backslash bmod\; (N\; \backslash times\; 2^)$. * If $H\; \backslash bmod(\; N\; \backslash times\; 2^L)$ is $S$ or an address that comes after $S$, the address is $H\; \backslash bmod\; (N\; \backslash times\; 2^L)$. To add a bucket: * Allocate a new bucket at the end of the table. * If $S$ points to the $N\; \backslash times\; 2^L$th bucket in the table, reset $S$ and increment $L$. * Otherwise increment $S$. The effect of all of this is that the table is split into three sections; the section before $S$, the section from $S$ to $N\; \backslash times\; 2^L$, and the section after $N\; \backslash times\; 2^L$. The first and last sections are stored using $H\; \backslash bmod\; (N\; \backslash times\; 2^)$ and the middle section is stored using $H\; \backslash bmod(\; N\; \backslash times\; 2^L)$. Each time $S$ reaches $N\; \backslash times\; 2^L$ the table has doubled in size. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Linear hashing」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.